import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/24 14:35
 */
public class 位运算 {

    /*
    * #problem 191 位1的个数
    * */
    // 1. 位运算，每次清零最低位的1，直到整个数为0
    public int hammingWeight(int n) {
        int count = 0;
        while( n != 0) {
            n = n&(n-1);
            count++;
        }
        return count;
    }

    // 2. 位运算
    public int hammingWeight2(int n) {
        int count = 0;
        for(int i =0;i<32;i++) {
            if((n & (1<<i)) != 0) {
                count++;
            }
        }
        return count;
    }

    /*
    * #problem 231 2的幂
    * */
    // 1. 位运算 判断一个数是否为n的幂次方
    public boolean isPowerOfTwo(int n) {
        // 2的幂次方 ==> 在二进制中表示的形式为 只有一位是1，其余都是0
        return n>0 && (n & (n-1)) ==0;
    }

    /*
    * #problem 190 颠倒二进制位
    * */
    // 1. 位运算
    public int reverseBits(int n) {
        // 记录每个1所在的位置
        int[] location = new int[32];
        for(int i=0;i<32;i++) {
            if((n & (1 << i)) != 0) {
                location[i] = 1;
            }
        }
        int res = 0;
        for(int i=0;i<32;i++) {
            if(location[i] != 0) {
                res = res | (1 << (31-i));
            }
        }
        return res;
    }

    // 2. 位运算
    public int reverseBits2(int n ) {
        int res = 0;
        for(int i =0;i<32 && n!= 0;i++) {
            res = res | (n & 1) << (31-i);
            n = n >>> 1;
        }
        return res;
    }

    /*
    * #problem 338 比特位计数
    * */
    // 1. 位运算
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for(int i = 1;i<=n;i++) {
            if((n & 1) == 0 ) {
                res[i] = res[i-1] + 1;
            } else {
                res[i] = res[i-1];
            }
        }
        return res;
    }

    private int countBit(int n) {
        int res = 0;
        while(n != 0) {
            n = n & (n-1);
            res ++;
        }
        return res;
    }

    /*
    * #problem 52 N皇后II
    * 返回解法数量
    * */
    // 1. DFS + 剪枝
    public int totalNQueens(int n) {
        return dfs(n,0,new HashSet<>(),new HashSet<>(),new HashSet<>());
    }

    private int dfs(int n, int x, Set<Integer> d1, Set<Integer>d2,Set<Integer> lines) {
        if(x == n) {
            return 1;
        }
        int res = 0;
        for(int y =0;y<n;y++) {
            if(d1.contains(x+y) || d2.contains(x-y) || lines.contains(y)) {
                continue;
            }
            d1.add(x+y);
            d2.add(x-y);
            lines.add(y);
            res += dfs(n,x+1,d1,d2,lines);
            d1.remove(x+y);
            d2.remove(x-y);
            lines.remove(y);
        }
        return res;

    }

    // 2.位运算
    public int totalNQueens2(int n) {
        return solveNQueens(n,0,0,0,0);
    }

    private int solveNQueens(int n,int x,int columns,int d1,int d2) {
        if(n == x) {
            return 1;
        }
        int res = 0;
        // 计算得到可以遍历的列
        int available = ((1<<n)-1) & (~(columns|d1|d2));
        // 遍历所有可行的列
        while (available != 0) {
            // 获取到最低位1的位置
            int position = available & (-available);
            // 去掉最低位的1
            available = available & (available-1);
            res += solveNQueens(n,x+1,columns|position,(d1|position) << 1,(d2|position) >> 1);
        }
        return res;
    }


    /*
    * #problem 51 N皇后
    * 使用位运算来解决
    * */
    private List<List<String>> res = new ArrayList<>();
    private List<String> temp = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {

        Map<Integer,String> situation = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for(int i =0;i<n;i++) {
            sb.append(".");
        }
        for(int i =0;i<n;i++) {
            sb.setCharAt(i,'Q');
            int pos = (1<<i);
            situation.put(pos,sb.toString());
            sb.setCharAt(i,'.');
        }
        nQueensDfs(n,0,0,0,0,situation);
        return res;

    }

    private void nQueensDfs(int n,int x,int d1,int d2,int columns,Map<Integer,String> situations) {
        if(n == x) {
            res.add(new ArrayList<>(temp));
            return ;
        }
        int available = ((1<<n)-1) & (~(d1|d2|columns));
        while(available != 0) {
            int position = available & (-available);
            // int column = Integer.bitCount(position - 1); ==> 确定1的位置
            available = available & (available-1);
            temp.add(situations.get(position));
            nQueensDfs(n,x+1,(d1|position) << 1,(d2|position) >> 1,columns | position,situations);
            temp.remove(temp.size()-1);

        }
    }

}
